การเปลี่ยนจากแบบวนซ้ำไปสู่การเรียกซ้ำ: การปรับโครงสร้างแนวคิด
การเรียกซ้ำ (Recursion) เป็นแนวทางที่เปลี่ยนแปลงมุมมองในการแก้ปัญหาอย่างแท้จริง ในการจัดการกับปัญหาเช่น การรวมผลรวมของรายการวิธีการวนซ้ำ(รายการรหัส 4-2) อาศัยตัวสะสมที่ชัดเจน theSum และควบคุมสถานะการวนซ้ำ; ในขณะที่วิธีการเรียกซ้ำนั้นอาศัยนิยามเชิงคณิตศาสตร์ที่ลึกซึ้ง:
$$listsum(numList) = first(numList) + listsum(rest(numList))$$
การเรียกซ้ำไม่ใช่แค่ฟังก์ชันที่เรียกตัวเอง แต่ยังแบ่งปัญหาที่ซับซ้อนออกเป็นปัญหาย่อยที่มีโครงสร้างเหมือนกันในขนาดเล็กลง จุดสำคัญคือการระบุความคล้ายกันระหว่างปัญหาใหญ่กับปัญหาย่อยความคล้ายกันการดำเนินการตามการเรียกซ้ำประกอบด้วยสองขั้นตอนที่สมมาตร:
- ขั้นตอน "ถอยไป": ตัดรายการเป็นส่วน ๆ และกดเข้าสู่สแต็กเรียกฟังก์ชันอย่างต่อเนื่อง จนกระทั่งถึงกรณีที่สามารถแก้ไขได้กรณีฐาน(Base Case)
- ขั้นตอน "กลับมา": เริ่มจากสถานะที่ง่ายที่สุด แล้วค่อย ๆ กลับขึ้นไปทีละระดับ และรวมผลลัพธ์เข้าด้วยกัน
ความเข้าใจหลัก
แนวคิดการวนซ้ำคือ "หยิบถังหนึ่งใบ ใส่เลขทีละตัวลงไปแล้วรวมกัน"; ขณะที่แนวคิดการเรียกซ้ำคือ "หากคุณบอกฉันได้ว่าผลรวมของจำนวนที่เหลืออยู่เท่าใด ฉันก็แค่เพิ่มตัวแรกเข้าไปก็พอ"